// -*- C++ -*-
//
//  This file is part of Siena, a wide-area event notification system.
//  See http://www.inf.usi.ch/carzaniga/siena/
//
//  Authors: Antonio Carzaniga
//  See the file AUTHORS for full details. 
//
//  Copyright (C) 2003-2004 University of Colorado
//
//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License
//  as published by the Free Software Foundation; either version 2
//  of the License, or (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
//  USA, or send email to one of the authors.
//
//
// $Id: bset.h,v 1.10 2010-03-11 15:16:39 carzanig Exp $
//
#ifndef BSET_H
#define BSET_H

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "ConstsSff.h"
#include <climits> // for CHAR_BIT
#ifdef DEBUG_OUTPUT
#include <iostream>
#endif

#include "bitcounter.h"

/** \file bset.h 
 *
 *  This file defines the Bloom filter types used in the BTable
 *  forwarding table implementation.
 *  
 *  We have two implementations of a Bloom filter.  The first
 *  implementation uses the bitset template of the C++ standard
 *  library.  The second implementation uses an ad hoc data structure
 *  designed to be as simple and compact as possible, and therefore
 *  (hopefully) as fast as possible.  You can choose which
 *  implementation to use at "configure" time.  The default is to use
 *  the "ad hoc" implementation.  However, you can switch to the
 *  "standard" implementation by passing --enable-std-bitset
 *  command-line option to the configure script.
 **/
namespace siena {
    //
    // REMINDER:  the methods required by bset_encoding.h are:
    //
    // set_bit(unsigned int i)  :: sets the i-th bit
    // unsigned int b.size()    :: size of the Bloom filters in bits
    // 

//
// I guess M must be a multiple of 64...
//
template <unsigned M>
class bset {
private:
    //
    // this data structure represents a bit vector.  The idea is
    // obviously to represent it using the most efficient integral
    // type available on the machine, so as to parallelize bit-wise
    // operation, and to reduce memory access as much as possible.
    //
    // The building block of the data structure is block_t.  The bit
    // vector is then represented as an array of one or more block_t
    // values.
    //
    typedef unsigned long block_t;

    // number of bits in a block_t
    //
    static const unsigned int BlockBitSize = (sizeof(block_t) * CHAR_BIT);

    // I'm assuming that BlockBitSize is a power of two
    //
    static const unsigned int BlockBitMask = (BlockBitSize - 1);

    // I'm assuming sizeof(block_t) is either 8 or 4
    //
    static const unsigned int BlockBitShift = (sizeof(block_t) == 8) ? 6 : 5;

    // number of blocks needed to represent M bits.  Notice that I'm
    // assuming that M = 0 mod BlockBitSize.
    //
    static const unsigned int BVSize = (M / BlockBitSize);

    static unsigned int block_index(unsigned int pos) {
	return pos >> BlockBitShift;
    }

    static unsigned int bit_index(unsigned int pos) {
	return pos & BlockBitMask;
    }

    block_t bv[BVSize];

public:
    static unsigned int size() { return M; }
    typedef unsigned char byte_t;

    // number of 8-bit blocks
    //
    static const unsigned int B8Size = (M >> 3);

    bset() throw () {
	for(unsigned int i = 0; i < BVSize; ++i)
	    bv[i] = 0;
    }

    bset(const bset & x) throw () {
	for(unsigned int i = 0; i < BVSize; ++i)
	    bv[i] = x.bv[i];
    }

    bset & operator = (const bset & x) throw () {
	for(unsigned int i = 0; i < BVSize; ++i)
	    bv[i] = x.bv[i];
	return *this;
    }

    void set_bit(unsigned int pos) {
        block_t m = 1;
	m <<= bit_index(pos);
        bv[block_index(pos)] |= m;
    }

    bool covers(const bset & s) const throw () {
	for(unsigned int i = 0; i < BVSize; ++i)
	    if ((bv[i] & s.bv[i]) != s.bv[i]) return false;
        return true;
    }

    bool operator[](unsigned pos) const {
        block_t m = 1;
	m <<= bit_index(pos);
        return bv[block_index(pos)] & m;
    }

    /** @brief counts the number of elements (i.e., bits == 1) in the
     *  bitset. 
     */
    unsigned int count() const { 
	register unsigned char res = 0;
	for(unsigned int i = 0; i < BVSize; ++i) {
	    register block_t x = bv[i];
	    while(x) {
		res += BitCounterMap[x & BitCounterMapMask];
		x >>= BitCounterMapShift;
	    }
	}
	return res;
    }
    /** \brief 8-bit block (byte) at position pos
     */
    byte_t bv8(unsigned int pos) const throw() {
#ifdef DO_NOT_REINTERPRET_CAST_BV
	unsigned shamt = (pos & (BlockBitMask >> 3)) << 3;
	return (bv[pos >> (BlockBitShift - 3)] >> shamt) & 0xff;
#else
	return reinterpret_cast<const byte_t *>(bv)[pos];
#endif
    }
};

static const unsigned int BSize = CONFIG_BLOOM_FILTER_SIZE;
typedef bset<BSize> bset_t;

#ifdef DEBUG_OUTPUT
template <unsigned M>
std::ostream & operator << (std::ostream & os, const bset<M> & b) {
    for(unsigned int i = 0; i < M; ++i)
	os << (b[i] ? '1' : '0');
    return os;
}
#endif

} // end namespace siena

#endif
